package Offer32;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印
 *
 * @author 23737
 * @time 2021.9.8
 */
public class Text_one {
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2 = new TreeNode(9);
        TreeNode treeNode3 = new TreeNode(20);
        TreeNode treeNode4 = new TreeNode(15);
        TreeNode treeNode5 = new TreeNode(7);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.left = treeNode4;
        treeNode3.right = treeNode5;
        int[] ints = new classSolutionTwice().levelOrder(treeNode1);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class SolutionOne {
    public int[] levelOrder(TreeNode root) {
        //判断队列是否为空，如果为空，则直接返回一个空数组
        if (root == null) {
            return new int[0];
        }
        //实例化一个队列，二叉树层序遍历（BFS）的问题一般用二叉树来解决
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //创建一个集合来进行节点的存储
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (!queue.isEmpty()) {
            //先弹出队首的元素
            TreeNode node = queue.poll();
            //集合保存弹出队首元素的值
            arrayList.add(node.val);
            //判断左右结点是否为空，如果为空不添加，不为空添加左右结点
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        //最后将集合的值复制到数组中去
        int[] array = new int[arrayList.size()];
        for (int i = 0; i < array.length; i++) {
            array[i] = arrayList.get(i);
        }
        return array;
    }
}

/**
 * 二刷
 * 个人写
 */
class classSolutionTwice{
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<TreeNode> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            list.add(poll);
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null){
                queue.add(poll.right);
            }
        }
        int[] ints = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ints[i] = list.get(i).val;
        }
        return ints;
    }
}





